Theo dự tính của Aguilera thì "Candyman" sẽ được chọn là đĩa đơn thứ hai trích từ Back to Basics nhưng hãng RCA lại chọn "Hurt" với hy vọng nó sẽ thành công như "Beautiful" năm 2002. Đĩa đơn được phát hành vào ngày 5 tháng 2 năm 2007 ở Mỹ mặc dù Aguilera đã quảng bá bằng cách trình diễn bài hát tại đêm New Year's Rockin' Eve. Bài hát lọt vào Billboard Hot 100 lần đầu tiên vào ngày 20 tháng 1 trước khi phát hành dưới dạng đĩa đơn và sau 7 tuần ở trên bảng xếp hạng, "Candyman" đạt vị trí #25. Ở Anh, bài hát đạt vị trí #17 với hơn 100.000 lượt tải. Nhưng bài hát mới thật sự thành công nhất khi đều đạt vị trí #2 ở Úc và New Zealand.